import datastructurelike.ListNode;
import datastructurelike.TreeNode;


import java.util.*;

public class Soulution {



    // 最长无重复子串的长度
    public int maxLength (int[] arr) {
        // write code here
        HashMap<Integer, Integer> map = new HashMap<>();
        int max=0;
        for(int start=0,end=0;end<arr.length;end++){
            if(map.containsKey(arr[end])){
                start=Math.max(start,map.get(arr[end])+1);
            }

            max=Math.max(max,end-start+1);
            map.put(arr[end],end);
        }
        return max;
    }
    // 二分查找
    public int search (int[] nums, int target) {
        // write code here
        int start=0;
        int end=nums.length;

        while (start<=end){
            int pos=start+(end-start)/2;

            if(nums[pos]<target){
                start=pos+1;
            }else if(nums[pos]>target) {end=pos-1;}
            if(nums[pos]==target){
                return pos;
            }
        }
        return -1;
    }

    // 快速排序
    public int[] MySort (int[] arr) {
        // write code here
        arr =  quickSort(arr, 0, arr.length-1);
        return arr;
    }

    //一次排序
    public int[] quickSort(int[] arr, int low , int high){
        if(low>=high) return arr;

        int i=low, j = high, temp = arr[low];

        while(i<j){
            while(i<j && arr[j]>temp) {
                j--;
            }
            if(i<j) {
                arr[i++] = arr[j];
            }

            while(i<j && arr[i]<temp) {
                i++;
            }
            if(i<j) {
                arr[j--] = arr[i];
            }
        }
        arr[i] = temp;
        arr = quickSort(arr, low, i-1);
        arr = quickSort(arr, j+1, high);
        return arr;
    }

    // 括号匹配

    /**
     *
     * @param s
     * @return
     * 遍历字符串，匹配到左括号时，将对应的右括号进栈，
     * 当匹配到右括号时，弹出栈顶元素看是否一致，诺栈为空或不一致时，无效括号序列
     * 遍历完栈为空时，则为有效括号序列
     *
     */

    public boolean isValid (String s) {
        // write code here
        Stack<Character> stack = new Stack<Character>();
        for(char c : s.toCharArray()){
            if(c=='(') {
                stack.push(')');
            } else if(c=='[') {
                stack.push(']');
            } else if(c=='{') {
                stack.push('}');
            } else if(stack.empty() || stack.pop()!=c) {
                return false;
            }
        }
        return stack.empty();
    }

    // 跳台阶
    public int jumpFloor(int target) {

        int d1 = 1, d2 = 1;
        while(target-- > 1 ){
            int temp = d2;
            d2 = d2 + d1;
            d1 = temp;
        }
        return d2;

    }

    /** 链表是否有环
     * Definition for singly-linked list.
     * class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) {
     *         val = x;
     *         next = null;
     *     }
     * }
     */

    public boolean hasCycle(ListNode head) {
       ListNode slowPointer=head;
       ListNode quickPointer=head;
       while (quickPointer!=null && quickPointer.next!=null){
           slowPointer=slowPointer.next;
           quickPointer=quickPointer.next.next;
           if (slowPointer==quickPointer) {
               return true;
           }

       }
       return false;
    }



    /*
     * public class TreeNode {
     *   int val = 0;
     *   TreeNode left = null;
     *   TreeNode right = null;
     * }
     */


    /** 最近公共祖先
     *
     * @param root TreeNode类
     * @param o1 int整型
     * @param o2 int整型
     * @return int整型
     */
    public int lowestCommonAncestor (TreeNode root, int o1, int o2) {
        // write code here

        TreeNode result =commonNode(root,o1,o2);
        if(result == null){
            return -1;
        }
        return result.val;

    }

;    public TreeNode commonNode(TreeNode node, int o1, int o2){
        if(node == null || node.val ==o1 || node.val == o2){
            return node;
        }
        TreeNode left = commonNode(node.left, o1, o2);
        TreeNode right = commonNode(node.right, o1, o2);
        if(left ==null){
            return right;
        }
        if(right ==null){
            return left;
        }
        return node;
    }

    // 合并有序数组
    public void merge(int A[], int m, int B[], int n) {
        //因为题目明确说了A数组足够大，所以直接在A数组操作
        int i = m - 1;
        int j = n - 1;
        int index = m + n - 1;
        //AB合并后最后一个元素所在位置
        while(i >= 0 && j >= 0)
            //AB合并，谁大就先放谁
        {
            A[index --] = A[i] > B[j] ? A[i --] : B[j --];
        }
        while(j >= 0)//如果B没有遍历完，那么之间丢在A数组里面
        {
            A[index --] = B[j --];
        }

    }
    //两数之和
    //O(n)复杂度，遍历一遍，找到解就返回，没找到就放入map，key是值，value是下标加1；
    public static int[] twoSum(int[] numbers, int target) {
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        for(int i = 0; i < numbers.length; i++) {
            if(map.containsKey(target - numbers[i])) {
                return new int[]{map.get(target - numbers[i]), i+1};
            }
            map.put(numbers[i], i+1);
        }
        return null;
    }



    //
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null) {
            return null;
        }

        ListNode cur = head;
        while (cur.next != null) {
            if (cur.val == cur.next.val) {
                cur.next = cur.next.next;
            } else {
                cur = cur.next;
            }
        }

        return head;
    }

    /**
     * 移除链表第n个节点
     *
     * @param head 头
     * @param n    n
     * @return {@link ListNode}
     */
    public ListNode removeNthFromEnd (ListNode head, int n) {
        ListNode dum=new ListNode(0);
        dum.next=head;
        ListNode cur=dum,pos=dum;

        for(int i=0;i<=n;i++){
            pos=pos.next;
        }
        while(pos!=null){
            pos=pos.next;
            cur=cur.next;
        }

        cur.next=cur.next.next;
        return dum.next;

    }

    /**
     * 之字形打印二叉树
     *
     * @param pRoot p根
     * @return {@link ArrayList<ArrayList<Integer>>}
     */
    public ArrayList<ArrayList<Integer> > print(TreeNode pRoot) {
        //解题思路是使用两个栈，同时判断奇偶，奇数层先放左节点再放右节点；
        ArrayList<ArrayList<Integer>>  ans  = new  ArrayList<ArrayList<Integer>>();
        if(pRoot==null) {
            return  ans;
        }
        Stack<TreeNode>  stack1 =  new Stack<>();
        stack1.push(pRoot);
        Stack<TreeNode>  stack2 =  new Stack<>();
        while(!stack1.isEmpty() || !stack2.isEmpty()){
            if(!stack1.isEmpty()){
                ArrayList<Integer>  tmp  = new  ArrayList<>();
                while(!stack1.isEmpty()){
                    TreeNode  p  =  stack1.pop();
                    tmp.add(p.val);
                    if(p.left!=null) {
                        stack2.add(p.left);
                    }
                    if(p.right!=null) {
                        stack2.add(p.right);
                    }
                }
                ans.add(tmp);
            }else{
                ArrayList<Integer>  tmp  = new  ArrayList<>();
                while(!stack2.isEmpty()){
                    TreeNode p =  stack2.pop();
                    tmp.add(p.val);
                    if(p.right!=null){
                        stack1.add(p.right);
                    }
                    if(p.left!=null){
                        stack1.add(p.left);
                    }
                }
                ans.add(tmp);
            }
        }
        return  ans;
    }
    /*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/

    public ListNode ReverseList(ListNode head) {

        if(head==null) {
            return null;
        }
        ListNode cur=head;
        ListNode pre = null;
        ListNode next = cur.next;


        while(cur.next!=null){
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }

    /**
     * 得到最小数字解
     * 题目的思路还是非常简单的：维持一个K长度的最小值集合，然后利用插入排序的思想进行对前K个元素的不断更新。
     * @param k     k
     * @return {@link ArrayList<Integer>}
     *///最小的k个数
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {

        ArrayList<Integer> result = new ArrayList<Integer>();
        if(k<= 0 || k > input.length) {
            return result;
        }
        //初次排序，完成k个元素的排序
        for(int i = 1; i< k; i++){
            int j = i-1;
            int unFindElement = input[i];
            while(j >= 0 && input[j] > unFindElement){
                input[j+1] = input[j];
                j--;
            }

            input[j+1] = unFindElement;
        }
        //遍历后面的元素 进行k个元素的更新和替换
        for(int i = k; i < input.length; i++){
            if(input[i] < input[k-1]){
                int newK = input[i];
                int j = k-1;
                while(j >= 0 && input[j] > newK){
                    input[j+1] = input[j];
                    j--;
                }
                input[j+1] = newK;
            }
        }
        //把前k个元素返回
        for(int i=0; i < k; i++) {
            result.add(input[i]);
        }
        return result;
    }
    public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {
        ArrayList<ArrayList<Integer>> res = new ArrayList();//用于返回最后的结果
        if(root == null) {
            return res;//如果根节点为空就返回结果
        }
        Queue<TreeNode> q = new LinkedList<TreeNode>();//用于存储每一层的节点
        q.add(root);
        while(!q.isEmpty()){
            int n = q.size();
            ArrayList<Integer> temp = new ArrayList<>();//用于存储当前遍历这一层的节点
            for(int i = 0;i < n;i ++){
                TreeNode node = q.poll();//取出队列的第一个元素
                temp.add(node.val);//将队头元素保存起来
                if(node.left != null) {
                    q.add(node.left);//左孩子如果不为空就进队列
                }
                if(node.right != null) {
                    q.add(node.right);//右孩子如果不为空就进队列
                }
            }
            res.add(temp);//将这一层的节点数里面据保存到res
        }
        return res;
    }
    public static void main(String[] args) {
        Soulution soulution = new Soulution();
        String ans=soulution.toString();
        System.out.println(ans);
    }

}
